package cn.initcap.algorithm.data.structures.lrucache;

import java.util.HashMap;
import java.util.Map;

/**
 * @author initcap
 * @date Created in 2020/4/29 08:36.
 */
public class LruCache {

    private Map<Integer, Node> map;
    private DoubleList cache;
    private int capacity;

    public LruCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        } else {
            int val = map.get(key).val;
            // 将当前key移动到前边
            put(key, val);
            return val;
        }
    }

    public void put(int key, int val) {
        Node x = new Node(key, val);
        if (map.containsKey(key)) {
            // 删除旧节点
            cache.remove(map.get(key));
            // 将新节点插入到开头
            cache.addFirst(x);
            map.put(key, x);
        } else {
            // 如果cache已经满了，删除最后一个位置，删除map中映射到该数据的键
            if (cache.size() == capacity) {
                // 删除链表最后一个数据
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            // 直接添加到头部
            cache.addFirst(x);
            map.put(key, x);
        }
    }

    class Node {
        public int key,val;

        public Node next, prev;

        public Node(int k, int v) {
            this.key = k;
            this.val = v;
        }

        public Node() {
            this.key = 0;
            this.val = 0;
        }
    }

    class DoubleList {

        private Node head, tail;
        private int size;

        public DoubleList() {
            this.head = new Node();
            this.tail = new Node();
            head.next = tail;
            tail.prev = head;
            this.size = 0;
        }

        /**
         * 在链表头部添加节点x,时间复杂度O(1)
         * @param x 节点
         */
        public void addFirst(Node x) {
            Node next = head.next;
            head.next = x;
            x.next = next;
            x.prev = head;
            next.prev = x;
            size++;
        }

        public void remove(Node x) {
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;
        }

        public Node removeLast() {
            Node remove = tail.prev;
            tail.prev = tail.prev.prev;
            tail.prev.next = tail;
            size--;
            return remove;
        }

        public int size() {
            return size;
        }
    }

}
